package com.example.maze;

import java.util.ArrayList;

public class SpanningTree {
   static ArrayList<Edge> graph       = new ArrayList<Edge>();
   static ArrayList<Edge> spanningTree= new ArrayList<Edge>();
   static int             M,N;
   static Vertex[][]      vertexes;
   static int[]           vertexGrpNum;                   // recovery grpNum
   
   public static void setData(int _M,
                              int _N,
                              Vertex[][] VERTEXES,
                              ArrayList<Edge> GRAPH) {  
      M= _M;
      N= _N;
      int index   = 0;
      vertexes    = new Vertex[M][N];
      vertexGrpNum= new int[M*N];      
      for(int i=0; i<M; i++) {                            // 抄一份, 但 vertex的 grpNum接下來無可避免會被修改
         for(int j=0; j<N; j++) {
            vertexes[i][j]= VERTEXES[i][j];
            vertexGrpNum[index++]= VERTEXES[i][j].grpNum; // recovery grpNum  
         }
      }      
      graph.clear();      
      for(Edge e: GRAPH) graph.add(e);                    // 抄一份, 避免直接取用      
   }
   
   private static int randNum(int r) {
      return (int)Math.round(Math.random()*r);
   }
   private static boolean check(Vertex v1, Vertex v2) { 
      return !(v1.grpNum == v2.grpNum);                   // 群組相異則回傳 true
   }
   private static void adjointGroup(Vertex v1, Vertex v2) {
      final int A_GROUP= v1.grpNum, 
                B_GROUP= v2.grpNum;
      for(int i=0; i<M; i++) {                            //找出 B群所有頂點, 將其加進 A群中
         for(int j=0; j<N; j++) {  
            if(vertexes[i][j].grpNum == B_GROUP)
               vertexes[i][j].grpNum= A_GROUP;               
         }   
      }     
   }
   public static ArrayList<Edge> getTree() {  
      spanningTree.clear();                                      
      Edge randomEdge;
      ArrayList<Edge> _graph= new ArrayList<Edge>();
      _graph.clear();
      for(Edge e: graph) _graph.add(e);                   // 在此抄一份 graph以供使用                            
      while(!_graph.isEmpty()) {
         randomEdge= _graph.get(randNum(_graph.size()-1));
         if(check(randomEdge.v1, randomEdge.v2)) {        // 確認 minCostEdge是否為 SpanningTree edge
            spanningTree.add(randomEdge); 
            adjointGroup(randomEdge.v1, randomEdge.v2);   // 重新調整群組
         }        
         _graph.remove(_graph.indexOf(randomEdge));
      }
      int index= 0;
      for(int i=0; i<M; i++) {                            // recovery grpNum
         for(int j=0; j<N; j++) {  
            vertexes[i][j].grpNum= vertexGrpNum[index++];               
         }   
      }      
      return spanningTree;
   }
   
//   public static ArrayList<Edge> recovery(ArrayList<Edge> mGraph, long[] indexArr) {
//      spanningTree.clear(); 
//      int lengthOfArray= indexArr.length;
//      for(int i=0; i<lengthOfArray; i++) {
//         for(Edge edge: mGraph) {
//            if(indexArr[i] == edge.index()) {
//               spanningTree.add(edge);
//               break;
//            }
//         }
//      }
//      return spanningTree;
//   }
}